//给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充
//。
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O",
//"X","X"]]
//输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
//解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都
//会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
// 
//
// 示例 2： 
//
// 
//输入：board = [["X"]]
//输出：[["X"]]
// 
//
// 
//
// 提示： 
//
// 
// m == board.length 
// n == board[i].length 
// 1 <= m, n <= 200 
// board[i][j] 为 'X' 或 'O' 
// 
// 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 824 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

class SurroundedRegions {
    public static void main(String[] args) {
        Solution solution = new SurroundedRegions().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 并查集
        // https://labuladong.gitee.io/algo/2/22/53/
        /*public void solve(char[][] board) {
            if (board.length == 0) return;
            int m = board.length;
            int n = board[0].length;

            UF uf = new UF(m * n + 1);
            // 设置虚拟头节点，用来连接边上的O
            int dummy = m * n;

            // 连接左右边不满足的0
            for (int i = 0; i < m; i++) {
                if (board[i][0] == 'O') {
                    uf.union(i * n, dummy);
                }

                if (board[i][n - 1] == 'O') {
                    uf.union(i * n + n - 1, dummy);
                }
            }

            for (int j = 0; j < n; j++) {
                if (board[0][j] == 'O') {
                    uf.union(j, dummy);
                }

                if (board[m - 1][j] == 'O') {
                    uf.union((m - 1) * n + j, dummy);
                }
            }

            // 定义上下左右方向数组
            int[][] d = new int[][]{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
            // 去掉边开始搜索
            for (int i = 1; i < m - 1; i++) {
                for (int j = 1; j < n - 1; j++) {
                    if (board[i][j] == 'O') {
                        // 将O与上下左右的相连
                        for (int k = 0; k < d.length; k++) {
                            int x = i + d[k][0];
                            int y = j + d[k][1];
                            if (board[x][y] == 'O')
                                uf.union(x * n + y, i * n + j);
                        }
                    }
                }
            }

            // 所有不和 dummy 连通的 O，都要被替换
            for (int i = 1; i < m - 1; i++) {
                for (int j = 1; j < n - 1; j++) {
                    if (!uf.connected(dummy, i * n + j)) {
                        board[i][j] = 'X';
                    }
                }
            }
        }

        // 并查集类
        class UF {
            // 连通分量个数
            private int count;
            // 存储每个节点的父节点
            private int[] parent;

            public UF(int n) {
                this.count = n;
                parent = new int[n];
                for (int i = 0; i < n; i++) {
                    // 指向自己
                    parent[i] = i;
                }
            }

            // 是否连通
            public boolean connected(int p, int q) {
                // 找到根节点进行比较
                int rootP = find(p);
                int rootQ = find(q);
                return rootP == rootQ;
            }

            // 将两个节点相连
            public void union(int p, int q) {
                // 找到根节点进行比较
                int rootP = find(p);
                int rootQ = find(q);

                if (rootP == rootQ) return;

                parent[rootQ] = rootP;

                // 两个连通分量合并成一个连通分量
                count--;
            }

            // 找到父节点，并优化为一层的树
            public int find(int x) {
                if (parent[x] != x) {
                    parent[x] = find(parent[x]);
                }

                return parent[x];
            }

            public int count() {
                return count;
            }
        }*/


        // DFS 岛屿问题，先遍历边界的O，标记为A，再遍历所有，遇到A设置为O，遇到O设置为X
        // https://leetcode.cn/problems/surrounded-regions/solution/bei-wei-rao-de-qu-yu-by-leetcode-solution/
        public void solve(char[][] board) {
            // 处理左右
            for (int i = 0; i < board.length; i++) {
                dfs(board, i, 0);
                dfs(board, i, board[0].length - 1);
            }

            for (int i = 0; i < board[0].length; i++) {
                dfs(board, 0, i);
                dfs(board, board.length - 1, i);
            }

            // 处理标记了的
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (board[i][j] == 'A') {
                        board[i][j] = 'O';
                    } else if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                }
            }
        }

        public void dfs(char[][] board, int i, int j) {
            if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'O') return;
            // 做一个标记
            board[i][j] = 'A';
            dfs(board, i + 1, j);
            dfs(board, i - 1, j);
            dfs(board, i, j + 1);
            dfs(board, i, j - 1);
        }

        // BFS
        /*int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        public void solve(char[][] board) {
            int m = board.length, n = board[0].length;
            Queue<int[]> queue = new LinkedList<>();
            // 上下左右加入队列
            for (int i = 0; i < m; i++) {
                if (board[i][0] == 'O') {
                    queue.offer(new int[]{i, 0});
                    board[i][0] = 'A';
                }

                if (board[i][n - 1] == 'O') {
                    queue.offer(new int[]{i, n - 1});
                    board[i][n - 1] = 'A';
                }
            }

            // 注意边界，避免重复
            for (int j = 1; j < n - 1; j++) {
                if (board[0][j] == 'O') {
                    queue.offer(new int[]{0, j});
                    board[0][j] = 'A';
                }

                if (board[m - 1][j] == 'O') {
                    queue.offer(new int[]{m - 1, j});
                    board[m - 1][j] = 'A';
                }
            }

            while (!queue.isEmpty()) {
                int[] poll = queue.poll();
                int x = poll[0], y = poll[1];
                for (int i = 0; i < 4; i++) {
                    int x1 = x + dx[i], y1 = y + dy[i];
                    if (x1 < 0 || y1 < 0 || x1 >= m || y1 >= n || board[x1][y1] != 'O') continue;
                    queue.offer(new int[]{x1, y1});
                    board[x1][y1] = 'A';
                }
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'A') {
                        board[i][j] = 'O';
                    } else if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                }
            }
        }*/

    }
//leetcode submit region end(Prohibit modification and deletion)

}
